console.log("20210915!!!")



// 算法经典题目
const array = [8, 5, 6, 3, 5, 3, 7, 9, 10, 21, 52]


function bubbleSort (array) {

    const length = array.length
    if(length <= 1){
        return array
    }

    const swap = (arr, i, j) => {
        const temp = arr[j]
        arr[j] = arr[i]
        arr[i] = temp 
    }

    for(let i = 0; i < length; i++){
        for(let j = 1; j < length - i; j++){
            if(array[j] < array[j - 1]){
                swap(array, j, j - 1)
            }
        }
    }

    return array
}

function insertSort(array) {

    if(array.length <= 1){
        return array
    }

    const selectMin = (array) => {
        const min = array.reduce((min, number, index) => {
            return number < array[min] ? index: min
        }, 0)

        const minNum = array[min]
        array.splice(min, 1)

        return minNum
    }

    let arr = []
    while(array.length > 0){
        const min = selectMin(array)
        arr.push(min)
    }

    return arr
    
}

function quickSort(array) {
    if(array.length <= 1){
        return array
    }

    const swap = (arr, i, j) => {
        const temp = arr[j]
        arr[j] = arr[i]
        arr[i] = temp

        return i
    }

    let len = array.length
    let flag = 0
    let i = 1
    let j = len - 1

    while(i < j){
        // 这里一定要先从后往前比较
        while(flag < j && array[flag] < array[j]) j--
        flag = swap(array, j, flag)

        while(i < flag && array[i] < array[flag]) i++
        flag = swap(array, i, flag)

    }

    const left = quickSort(array.slice(0, flag))
    const right = quickSort(array.slice(flag + 1, len))

    return left.concat(array[flag]).concat(right)
}


function quickSort2(array) {
    if(array.length <= 1){
        return array
    }
    let flag = array[0]

    // 考虑到首个元素
    const leftArray = array.filter((item,index) => (item <= flag && index !== 0))
    const rightArray = array.filter(item => (item > flag))

    const left = quickSort2(leftArray)
    const right = quickSort2(rightArray)

    return [...left, flag, ...right]
}


function mergeSort(array) {

    if(array.length <= 1){
        return array   
    }

    const flag = Math.floor(array.length/2)

    const left = mergeSort(array.slice(0, flag))
    const right = mergeSort(array.slice(flag, array.length))

    let arr = []
    while(left.length > 0 && right.length > 0){      
        if(left[0] < right[0]){
            arr.push(left[0])
            left.shift()
        } else {
            arr.push(right[0])
            right.shift()
        }
    }
    if(left.length > 0){
        arr = [...arr, ...left]
    }

    if(right.length > 0){
        arr = [...arr, ...right]
    }

    return arr
}

// const sortedArray = bubbleSort(array)
// const sortedArray = insertSort(array)
// const sortedArray = quickSort2(array)
const sortedArray = mergeSort(array)

console.log("sortedArray:", sortedArray)






const arr1 = [1,2,3,4,8,9,10]

const arr2 = [2,6,7,8,9]



function mergArrays (arr1, arr2) {

    let arr = []
    while(arr1.length > 0 && arr2.length > 0){
        if(arr1[0]> arr2[0]){
            arr.push(arr2[0])
            arr2.shift()
        } else {
            arr.push(arr1[0])
            arr1.shift()
        }
    }

    if(arr1.length > 0){
        arr = [...arr, ...arr1]
    }

    if(arr2.length > 0){
        arr = [...arr, ...arr2]
    }


    return arr
}




/**
 * Definition for singly-linked list.
 */
function ListNode(val, next) {
    this.val = (val===undefined ? 0 : val)
    this.next = (next===undefined ? null : next)
}

function setList (arr){
    let head = null
    let pre = null
    arr.map(val => {
        let node = new ListNode(val)
        if(pre){
            pre.next = node
        } else {
            head = node
        }
        pre = node
    })
    return head
}

let head = setList([-1,5,3,4,0])
console.log(head)

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var sortList = function(head) {
    if(head && head.next){

        let pre = null
        let node = sortList(head.next)
        let start = node
        while(node){
            if(head.val <= node.val){
                if(pre){
                    pre.next = head
                    head.next = node
                    return start
                }

                head.next = node
                return head
            }

            pre = node
            node = node.next
        }

        pre.next = head
        head.next = null
        return start
    }
    return head
};


console.log(sortList(head))

const nums = [-1,0,1,2,-1,-4]

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
 var threeSum = function(nums) {

    let twoSum = (nums, j) => {
        const target = 0 - nums[j]
        const len = nums.length
        let i = 0
        let map = {}
        while(i<len){
            if(i!==j){
                let number = nums[i]

                if(typeof map[number] !== "undefined"){
                    return [nums[map[number]], nums[i]]
                }
    
                map[target - number] = i
            }

            i++
        }

        return false
    }


    let j = 0
    let length = nums.length
    let arr = []
    while(j<length){
        let two = twoSum(nums, j)
        if(two){
            arr.push([nums[j], ...two])
        }
        j++
    }
    return arr
};


console.log(threeSum(nums))


/**
 * @param {number[]} nums
 * @return {number}
 */
 var removeDuplicates = function(nums) {
    let arr = nums.filter((number,index) => {
        if(index === 0){
            return true
        } else {
            return number === nums[index-1]?false:true
        }
    })


    return arr
};






console.log(removeDuplicates([0,0,1,1,1,2,2,3,3,4]))




/**
 * Definition for a binary tree node.
 */
 function TreeNode(val, left, right) {
     this.val = (val===undefined ? 0 : val)
     this.left = (left===undefined ? null : left)
     this.right = (right===undefined ? null : right)
}

let node31 = new TreeNode(2)
let node21 = new TreeNode(2, node31)
let node32 = new TreeNode(2)
let node22 = new TreeNode(2, node32)
let root = new TreeNode(1, node21, node22)

/**
 * @param {TreeNode} root
 * @return {boolean}
 */
 var isSymmetric = function(root) {
    if(!root){
        return null
    }

    if(root.left && root.right){
        let arr = []
        const leftTree = (arr, node) => {
            if(node){
                leftTree(arr, node.left)
                arr.push(node)
                leftTree(arr, node.right)     
            }
        }

        leftTree(arr, root.left)
        console.log("arr:", arr)

        const rightTree = (arr, right) => {
            if(right){
                rightTree(arr, right.left)
                let left = arr[arr.length - 1]
                if(right.val===left.val){
                    if(left.left && right.right && left.left.val === right.right.val){
                        arr.pop()
                    }

                    if(left.right && right.left && left.right.val === right.left.val){
                        arr.pop()
                    }
                }
                rightTree(arr, right.right)   
            }
        }

        rightTree(arr, root.right)

        return arr.length === 0
    }

    return false
};

console.log(isSymmetric(root))



/**
 * @param {TreeNode} root
 * @return {number}
 */
 var maxDepth = function(root) {
    if(!root){
        return 0
    }

    let left = 0
    let right = 0

    if(root.left){
        left = maxDepth(root.left) + 1
    }

    if(root.right){
        right = maxDepth(root.right) + 1
    }


    return Math.max(left, right)

};